package com.LeeCode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 缺失的第一个正数
 */

public class Code041 {
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println(new Code041().firstMissingPositive1(nums));
    }

    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int res = 1;
        while (set.contains(res)) {
            res++;
        }
        return res;
    }

    public int firstMissingPositive1(int[] nums) {
        int n = nums.length;
        // 第一阶段：元素归位
        for (int i = 0; i < n; i++) {
            // 当当前数字是正整数且在数组长度范围内，且未在正确位置时
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1); // 将其交换到正确位置
            }
        }
        // 第二阶段：查找第一个不匹配的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1; // 返回第一个不匹配的位置
            }
        }
        // 如果所有位置都匹配，说明缺失的是n+1
        return n + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
